package com.company.Graph;

import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}15:54
 */
public class PrimAlgorithm {
    public static void main(String[] args) {
        char[] data = new char[]{'A','B','C','D','E','F','G'};
        int verxs = data.length;
        int no = Integer.MAX_VALUE;
        int [][] weight = {
                {no,5,7,no,no,no,2},
                {5,no,no,9,no,no,3},
                {7,no,no,no,8,no,no},
                {no,9,no,no,no,4,no},
                {no,no,8,no,no,5,4},
                {no,no,no,4,5,no,6},
                {2,3,no,no,4,6,no}
        };
        MGraph mGraph = new MGraph(verxs);
        // 创建一个最小生成树的对象
        MinTree tree = new MinTree();
        tree.createGraph(mGraph,verxs,data,weight);
        tree.showGraph(mGraph);

        tree.prim(mGraph,0);
    }
}

// 创建最小生成树
class MinTree{
    //

    /**
     * 创建图的邻接矩阵
     * @param graph 图对象
     * @param verxs 图对应的顶点个数
     * @param data 图的各个顶点的值
     * @param weight 图的邻接矩阵
     */
    public void createGraph(MGraph graph,int verxs,char[] data,int[][] weight){
        for (int i = 0; i < verxs; i++){ // 顶点
            graph.data[i] = data[i];
            for (int j = 0; j < verxs; j++){
                graph.weight[i][j] = weight[i][j];
            }
        }
    }

    // 显示图的邻接矩阵
    public void showGraph(MGraph graph){
        for (int[] link: graph.weight){
            System.out.println(Arrays.toString(link));
        }
    }

    // 编写Prim算法，得到最小生成树
    public void prim(MGraph graph,int v){
        int[] visited = new int[graph.verx];
        visited[v] = 1;
        // h1 h2 记录选中边的顶点
        int h1 = -1;
        int h2 = -1;
        char[] data = graph.data;
        int[][] weight = graph.weight;
        int min = Integer.MAX_VALUE;
        // 开始进行选择
        for (int k = 1; k < graph.verx; k++){// k是边的条数 是点数 - 1所以从1开始
            for (int i = 0; i < graph.verx; i++){// 选了的点
                for (int j = 0; j < graph.verx; j++){// 没选的点
                    if (visited[i] == 1 && visited[j] == 0 && weight[i][j] < min){
                        min = weight[i][j];
                        h1 = i;
                        h2 = j;
                    }
                }
            }
            System.out.println(data[h1] + "->" + data[h2] + ":" + weight[h1][h2]);
            min = Integer.MAX_VALUE;
            visited[h2] = 1;
        }
//        int[] visited = new int[graph.verx];
//        // 把当前节点设置为已访问
//        visited[v] = 1;
//        // h1和h2记录两个顶点的下标
//        int h1 = -1;
//        int h2 = -1;
//        int minWeight = Integer.MAX_VALUE;
//        // 确定每一次生成的子图，和哪个节点的距离最近
//        for (int k = 1; k < graph.verx; k++){// 因为Prim算法结束后，有顶点个数 - 1条边
//            // 每次都要全部扫描一遍 不知道能不能优化一下
//            for (int i = 0; i < graph.verx; i++){ // i节点表示被访问过的节点
//                for (int j = 0; j < graph.verx; j++){// j节点表示没有被访问过的节点
//                    if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight){
//                        minWeight = graph.weight[i][j];
//                        h1 = i;
//                        h2 = j;
//                    }
//                }
//            }
//            // 这就找到一条边最小
//            System.out.println("边" + graph.data[h1] + " - >" + graph.data[h2] + "> 权值" + minWeight);
//            visited[h2] = 1;
//            // 重新设置 minWeight；
//            minWeight = Integer.MAX_VALUE;
//        }
    }
}

class MGraph{
    int verx; // 表示图的节点个数
    char[] data; // 存放节点数据
    int[][] weight; // 存放边，就是我们的邻接矩阵

    public MGraph(int verx) {
        this.verx = verx;
        data = new char[verx];
        weight = new int[verx][verx];
    }
}
